In today's information age, communication devices, such as computers and computer peripherals, are often internetworked over a communication network. A common networking model routes packets of information within the communication network using a networking protocol such as the Internet Protocol (IP) or other network layer protocol. Some networking protocols, such as IP, are considered to be “connectionless” networking protocols. In a connectionless networking protocol, each packet of information includes a network layer address, and each router forwards the packet of information based upon the network layer address according to predetermined signaling and routing protocols, such as the Open Shortest Path First (OSPF) protocol, the Routing Information Protocol (RIP), Hello, Border Gateway Protocol (BGP), RSVP, or other routing protocol.
Thus, each router makes an independent forwarding decision for the packet based upon the network layer address. Essentially, each router partitions the entire set of network layer addresses into a number of Forwarding Equivalence Classes (FECs), and each FEC is mapped to a particular outgoing path (or set of paths, in the case of multi-path routing) based upon the routing protocol. The router determines an FEC for each packet of information based upon the network layer address of the packet, and forwards the packet of information to the corresponding outgoing path (or set of paths).
Network layer routing requires each router to process each packet of information at the network layer. This is an expensive and time-consuming operation that limits the performance of some routers and even prevents certain devices that do not support the networking protocol from performing routing and other functions on the packets.
Label switching can be used to eliminate the network layer processing by certain devices in the communication network. Label switching enables a packet to be transported across a network domain (referred to hereinafter as an “autonomous system” or “AS”) using labels rather than the network layer address. Specifically, a label switched path (LSP) is established from an ingress point border device to an egress point border device (often referred to individually as a “Label Edge Router” or “LSR”) in the AS. The LSP traverses a number of intermediate label switching devices (often referred to individually as a “Label Switching Router” or “LSR”). When the packet enters the ingress LER, the ingress LER uses the network address to assign the packet to a particular FEC, and inserts the corresponding label into the packet, specifically within a label header. Each intermediate LSR along the LSP forwards the packet based upon the label. The egress LER removes the label from the packet and forwards the packet based upon the network address. Thus, only the LERs process the packet at the network layer, while the LSRs process the packet based upon the label only.
In order to establish and remove LSPs, the various label switching devices exchange label switching information using a signaling protocol. Label switching information can be exchanged using a dedicated label distribution protocol, or can be exchanged (“piggy-backed”) in other signaling and routing protocols, such as OSPF, IS-IS, and RIP.
Each label switching device maintains mapping information for mapping each FEC to a corresponding label. The label mapping information is typically maintained in the various forwarding/routing tables maintained by the label switching device. It is common for the label switching device to maintain a forwarding table for each incoming interface and a forwarding table for each outgoing interface. The label mapping information maintained by the label switching device in the incoming forwarding tables enables the label switching device to quickly forward received packets that include label switching information. The label mapping information maintained by the label switching device in the outgoing forwarding tables enables the label switching device to insert label switching information into packets. For convenience, a forwarding table that includes label mapping information may be referred to as a label information base (LIB).
An architecture for multi-protocol label switching (MPLS) is discussed in E. Rosen et. al., Multiprotocol Label Switching Architecture, Internet Engineering Task Force (IETF) Request For Comments (RFC) 3031, January 2001, which is hereby incorporated herein by reference in its entirety. One signaling protocol for exchanging label switching information for MPLS is commonly known as the Label Distribution Protocol (LDP). LDP is described in L. Andersson et. al., LDP Specification, Internet Engineering Task Force (IETF) Request For Comments (RFC) 3036, January 2001, which is hereby incorporated herein by reference in its entirety. An encoding technique for producing and processing labeled packets for MPLS is described in E. Rosen et. al., MPLS Label Stack Encoding, Internet Engineering Task Force (IETF) Request For Comments (RFC) 3032, January 2001, which is hereby incorporated herein by reference in its entirety.
MPLS can be used for providing Virtual Private Network (VPN) services. A VPN is commonly defined as an overlay network that is built over a public network infrastructure that provides the VPN user (client) a secure, private connection using tunneling, encryption, and authentication. VPNs can be built at layer 2 (L2) of the network, for example using technologies like X.25, Frame Relay, or ATM, or at layer 3 (L3) of the network, for example, over the Public Internet using the Internet Protocol (IP). For convenience, VPNs built at layer 2 of the network are often referred to as L2 VPNs, while VPNs built at layer 3 of the network using IP are often referred to as L3 VPNs or IP VPNs. Various architectures of L2 and L3 MPLS based VPNs are described in the following IETF drafts, which are hereby incorporated herein by reference in their entireties: draft-martini-12circuit-trans-mpls-08, draft-ietf-ppvpn-rfc2547bis-01, draft-ietf-ppvpn-12vpn-00, draft-kompella-ppvpn-12vpn-01, draft-lasserre-vkompella-ppvpn-vpls-00, draft-kompella-ppvpn-dtls-01, draft-khandekar-ppvpn-hvpls-mpls-00, draft-ouldbrahim-12vpn-lpe-01, and draft-ietf-ppvpn-vpn-vr-01.
A typical multi-service packet network supports different classes of traffic. For example, a MPLS-based VPN may support real-time voice and video traffic as well as best effort data traffic. In order to support different classes of traffic, different forwarding behaviors are typically applied to the different classes of traffic. An example of different forwarding behavior is queue scheduling priority. Specifically, a packet carrying real-time voice should be forwarded before a packet carrying best effort data, thereby resulting in less delay for the real-time packet.
A multi-service packet network may also offer subscribers different levels of service (i.e., service availability and quality). For example, a telecom carrier typically offers subscribers different levels of service, thereby allowing the telecom carrier to charge subscribers different tariff rates. Carriers can use this flexibility in tariff rates to bid aggressively when dealing with low-end subscribers while also offering excellent service to high-end subscribers. Different levels of service may experience different degrees of service availability and bandwidth guarantees. Within each level of service, it is still necessary to handle the different classes of traffic appropriately.
Different classes of traffic and different levels of service can be supported through careful traffic engineering and network management followed with active monitoring to ensure that the subscriber Service Level Agreements (SLAs) are met. For example, MPLS LSPs bearing traffic from a premium “Gold” service could be routed through uncongested portions of the network using manually provisioned Explicit Routes. These premium LSPs could be monitored to ensure the SLAs are met. Network administrators could “tweak” these LSPs or add network capacity and equipment to address any problems. Although this approach is relatively simple, it has considerable administrative costs. Specifically, traffic engineering and management rely on salaried network administrators. Furthermore, it is unclear how rapidly human operators can react to changes to network topology that affect subscriber service.
Global application of priority across all class types can prevent the service provider from offering bandwidth guarantees to any traffic class. This is because connections of higher priority traffic classes can preempt all connections of a lower priority traffic class. Bandwidth can be guaranteed on a traffic class basis, although such a solution does not provide for different levels of service for a particular class of traffic.
Separate networks can be used to support different classes of traffic and different levels of service. In this model of operation, subscribers that receive the same level of service share a network. Within each network, Differentiated Services (DiffServ) or other techniques are used to provide differentiation between different classes of traffic, such as voice, video, and elastic data. This does not imply that the service provider operates completely separate physical networks. A service provider could choose to construct logically separate networks, for example, using virtual routers. However, this strategy greatly increases the administrative complexity (and hence the cost) of operating the service provider's network. Specifically, if N routers are required to support a service for a single service level and there are S service levels, up to O(SN) virtual routers would be required deliver service. This translates into increased router provisioning, increased network complexity when performing network QAM, and increased workload in network planning. Furthermore, a strategy of separate networks does not adequately address the issue of differentiation on availability. In particular MPLS LSPs bearing traffic from a premium service cannot preempt LSPs bearing traffic from an inferior service.
In order to avoid the administrative complexity of managing separate physical or logical networks, service level differentiation can be accomplished using resource class (color), preemption priority, and link cost management. Specifically, links can be assigned to one or more resource classes, essentially “coloring” the link. In MPLS signaling protocols like RSVP-TE and CR-LDP, LSPs can be restricted to using links that have certain colors. Traffic of LSPs that serve subscribers of different levels of service can be separated by assigning them different administrative groups such that the LSPs are routed over different physical links. These LSPs can employ an existing technique, such as Differentiated Services (DiffServ), for traffic class differentiation for real time versus data applications. However, to address the issue of differentiation on availability, it is necessary to permit LSPs of a premium service to preempt LSPs of an inferior service. This can be achieved through a combination of color, preemption priority, and link cost management. Specifically, with reference to an example with a premium “Gold” service and a non-premium service, certain links are reserved for premium service by marking them usable by LSPs with only the “Gold” color, assigning these links low link costs, and engineering these links to be sufficiently large to carry offered “Gold” LSPs, while other links are marked usable by both premium and non-premium services by marking them usable by both “Gold” LSPs and other color LSPs and assigning these links higher link costs in order to prevent their use by “Gold” LSPs under normal conditions. With proper provisioning and engineering based on the guidelines above, under normal conditions, premium “Gold” LSPs are run entirely on “Gold” colored links and are isolated from non-premium traffic. Under network failure conditions, Gold LSPs can preempt non-premium LSPs on links marked with “Gold” and other colors corresponding to non-premium services. One problem with this solution is that, under network failure conditions, it is possible that LSPs of the premium service are mixed together with non-premium LSPs in the same link. Thus, any differentiation on the basis of forwarding quality provided in terms of different bandwidth guarantees may be lost during a failure condition. This solution also involves administratively complex rules for engineering and provisioning links.